from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
# 实现一个LRU缓存
# 前置实现 DoubleList 双向链表 保证Lru缓存的插入 O（1）
class Node():
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None
class DoubleList:
    def __init__(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
    # 链表尾部插入节点 -》 最近使用
    def addLast(self,node):
        temp = self.tail.prev
        temp.next = node
        node.next = self.tail
        self.tail.prev = node
        node.prev = temp
        self.size += 1


    # 链表删除元素
    def remove(self,node):
        p  = node.prev
        n  = node.next
        p.next = n
        n.prev = p
        self.size -= 1
    # 链表头部删除元素 -> 淘汰最久使用
    def removeFirst(self):
        if self.size == 0:
            return None
        first = self.head.next
        self.remove(first)
        return first

    # 查看链表的长度
    def size(self):
        return self.size
class LRUCache:
    def __init__(self,capacity):
        self.capacity = capacity
        self.cache = DoubleList()
        self.map = {}
    def get(self,key):
        if key not in self.map:
            return -1
        res = self.map[key]
        # 把节点设置最近使用
        self.makeRecently(res)
        return res.value

    def put(self,key,value):
        if key in self.map:
            self.deleteKey(key)
        if self.cache.size == self.capacity:
            #删除最久的元素
            self.removeLeastRecently()
        self.addRecently(key,value)

    def addRecently(self, key: int, val: int):
        x = Node(key, val)
        # 链表尾部就是最近使用的元素
        self.cache.addLast(x)
        # 别忘了在 map 中添加 key 的映射
        self.map[key] = x
    def removeLeastRecently(self):
        # 链表头部的第一个元素就是最久未使用的
        deletedNode = self.cache.removeFirst()
        # 同时别忘了从 map 中删除它的 key
        deletedKey = deletedNode.key
        self.map.pop(deletedKey)
    # 将节点设置成最近使用
    def makeRecently(self,node):
        self.cache.remove(node)
        self.cache.addLast(node)

    def deleteKey(self, key: int):
        x = self.map[key]
        # 从链表中删除
        self.cache.remove(x)
        # 从 map 中删除
        self.map.pop(key)
        


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    solution = LRUCache(2)
    solution.put(1,1)
    solution.put(2,2)
    solution.get(1)
    solution.put(3,3)
    print(solution.get(2))
    # your test code here